package ch04.shortest_path;

public class Dijkstra {
    private static int n;
    private static boolean[] vis;
    private static double[][] a;
    private static double[] dis;
    static final double INF = Double.MAX_VALUE;

    private static void init() {
        n = 10;
        dis = new double[n + 1];
        vis = new boolean[n + 1];
        a = new double[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            vis[i] = false;
            dis[i] = INF;
            for (int j = 1; j <= n; j++) {
                a[i][j] = INF;
            }
        }
    }

    private static void afterA() {
        for (int i = 1; i <= n; i++) {
            dis[i] = a[i][1];
        }
    }

    static void dijkstra() {
        vis[1] = true;
        dis[1] = 0;
        for (int i = 1; i <= n; i++) {
            int k = 0;
            //找出距离最近的点
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && (k == 0 || dis[j] < dis[k])) {
                    k = j;
                }
            }
            vis[k] = true;
            //松弛
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && dis[j] > dis[k] + a[k][j]) {
                    dis[j] = dis[k] + a[k][j];
                }
            }
        }
    }


    private static void initA() {
        a[1][2] = 5;
        a[2][1] = 5;

        a[3][2] = 2;
        a[2][3] = 2;

        a[5][8] = 9;
        a[8][5] = 9;

        a[1][3] = 1;
        a[3][1] = 1;

        a[4][7] = 7;
        a[7][4] = 7;

        a[5][9] = 3;
        a[9][5] = 3;

        a[2][8] = 4;
        a[8][2] = 4;

        a[1][5] = 2;
        a[5][1] = 2;

        a[6][8] = 3;
        a[8][6] = 3;

        a[9][10] = 5;
        a[10][9] = 5;

        a[7][10] = 4.5;
        a[10][7] = 4.5;

        a[7][3] = 2.5;
        a[3][7] = 2.5;
    }

    static void print() {
        for (int i = 1; i <= n; i++) {
            System.out.println("节点1到" + i + "的距离为：" + dis[i]);
        }
    }

    public static void main(String[] args) {
        init();
        initA();
        afterA();
        dijkstra();
        print();
    }
}
